package org.basis.algorithm.list;

import org.basis.algorithm.list.common.SingleNode;

import java.util.LinkedList;
import java.util.Stack;

/**
 * 回文链表
 *
 * @author Mr_wenpan@163.com 2021/12/13 22:22
 */
public class PalindromeList {

    public static void main(String[] args) {
        SingleNode<Integer> head = buildList();
        boolean flg = palindromeListByStack(head);
        boolean flg1 = palindromeListByQueue(head);
        System.out.println(flg);
        System.out.println(flg1);
    }

    public static SingleNode<Integer> buildList() {
        SingleNode<Integer> node1 = new SingleNode<>(1);
        SingleNode<Integer> node2 = new SingleNode<>(2);
        SingleNode<Integer> node3 = new SingleNode<>(3);
        SingleNode<Integer> node4 = new SingleNode<>(3);
        SingleNode<Integer> node5 = new SingleNode<>(2);
        SingleNode<Integer> node6 = new SingleNode<>(1);
        node1.next = node2;
        node2.next = node3;
        node3.next = node4;
        node4.next = node5;
        node5.next = node6;
        return node1;
    }

    /**
     * 通过栈来判断回文链表
     * 需要 O（n） 的额外空间
     */
    private static boolean palindromeListByStack(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return true;
        }
        SingleNode<Integer> cur = head;
        Stack<SingleNode<Integer>> stack = new Stack<>();
        while (cur != null) {
            stack.push(cur);
            cur = cur.next;
        }
        cur = head;
        while (!stack.isEmpty()) {
            SingleNode<Integer> pop = stack.pop();
            if (!pop.data.equals(cur.data)) {
                return false;
            }
            cur = cur.next;
        }

        return true;
    }

    /**
     * 通过快慢指针来判断回文链表（核心是要找到链表的中点位置）
     * 注意快慢指针的位置和快指针走到空的时候慢指针所在的位置是中点还是中点的下一个节点或上一个节点（需要按照链表节点个数的奇偶来仔细判断）
     * 需要 O（n / 2） 的额外空间，时间复杂度O（n）
     */
    private static boolean palindromeListByQueue(SingleNode<Integer> head) {
        if (head == null || head.next == null) {
            return true;
        }
        SingleNode<Integer> fast = head;
        SingleNode<Integer> slow = head;
        while (fast != null) {
            slow = slow.next;
            fast = fast.next == null ? null : fast.next.next;
        }

        // 此时慢指针一定在链表中点位置
        // LinkedList是一个先进先出的双向链表，可以当做队列用
        LinkedList<SingleNode<Integer>> queue = new LinkedList<>();
        while (slow != null) {
            queue.push(slow);
            slow = slow.next;
        }

        fast = head;
        while (!queue.isEmpty()) {
            SingleNode<Integer> pop = queue.pop();
            if (!fast.data.equals(pop.data)) {
                return false;
            }
            fast = fast.next;
        }

        return true;
    }


}
